#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
public:
    int findBottomLeftValue(TreeNode* root) 
    {
        if(root == nullptr)
        {
            return 0;
        }
        int result = root->val;
        queue<TreeNode*> q;
        q.push(root);
        int size = 1;
        while(!q.empty())
        {
            int sizeNew = 0;
            for(int i = 0; i < size; i++)
            {
                auto node = q.front();
                if(i == 0)
                {
                    result = node->val;
                }
                q.pop();
                if(node->left != nullptr)
                {
                    q.push(node->left);
                    sizeNew++;
                }
                if(node->right != nullptr)
                {
                    q.push(node->right);
                    sizeNew++;
                }
            }
            size = sizeNew;
        }
        return result;
    }
};

// 辅助函数：创建二叉树节点
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    Solution solution;
    
    cout << "=== LeetCode 513. 找树左下角的值 测试案例 ===" << endl;
    
    // 测试案例1: 示例1 - [2,1,3]
    cout << "\n测试案例1: [2,1,3]" << endl;
    TreeNode* root1 = createNode(2);
    root1->left = createNode(1);
    root1->right = createNode(3);
    
    int result1 = solution.findBottomLeftValue(root1);
    cout << "输入: [2,1,3]" << endl;
    cout << "输出: " << result1 << endl;
    cout << "期望: 1 (最底层最左边的节点)" << endl;
    
    // 测试案例2: 示例2 - [1,2,3,4,null,5,6,null,null,7]
    cout << "\n测试案例2: [1,2,3,4,null,5,6,null,null,7]" << endl;
    TreeNode* root2 = createNode(1);
    root2->left = createNode(2);
    root2->right = createNode(3);
    root2->left->left = createNode(4);
    root2->right->left = createNode(5);
    root2->right->right = createNode(6);
    root2->right->left->left = createNode(7);
    
    int result2 = solution.findBottomLeftValue(root2);
    cout << "输入: [1,2,3,4,null,5,6,null,null,7]" << endl;
    cout << "输出: " << result2 << endl;
    cout << "期望: 7 (最底层最左边的节点)" << endl;
    
    // 测试案例3: 只有一个节点 [1]
    cout << "\n测试案例3: [1]" << endl;
    TreeNode* root3 = createNode(1);
    
    int result3 = solution.findBottomLeftValue(root3);
    cout << "输入: [1]" << endl;
    cout << "输出: " << result3 << endl;
    cout << "期望: 1 (只有根节点)" << endl;
    
    // 测试案例4: 完全二叉树 [1,2,3,4,5,6,7]
    cout << "\n测试案例4: [1,2,3,4,5,6,7]" << endl;
    TreeNode* root4 = createNode(1);
    root4->left = createNode(2);
    root4->right = createNode(3);
    root4->left->left = createNode(4);
    root4->left->right = createNode(5);
    root4->right->left = createNode(6);
    root4->right->right = createNode(7);
    
    int result4 = solution.findBottomLeftValue(root4);
    cout << "输入: [1,2,3,4,5,6,7]" << endl;
    cout << "输出: " << result4 << endl;
    cout << "期望: 4 (最底层最左边的节点)" << endl;
    
    // 测试案例5: 只有左子树 [1,2,null,4,null,8]
    cout << "\n测试案例5: [1,2,null,4,null,8]" << endl;
    TreeNode* root5 = createNode(1);
    root5->left = createNode(2);
    root5->left->left = createNode(4);
    root5->left->left->left = createNode(8);
    
    int result5 = solution.findBottomLeftValue(root5);
    cout << "输入: [1,2,null,4,null,8]" << endl;
    cout << "输出: " << result5 << endl;
    cout << "期望: 8 (最底层最左边的节点)" << endl;
    
    // 测试案例6: 只有右子树 [1,null,3,null,7,null,15]
    cout << "\n测试案例6: [1,null,3,null,7,null,15]" << endl;
    TreeNode* root6 = createNode(1);
    root6->right = createNode(3);
    root6->right->right = createNode(7);
    root6->right->right->right = createNode(15);
    
    int result6 = solution.findBottomLeftValue(root6);
    cout << "输入: [1,null,3,null,7,null,15]" << endl;
    cout << "输出: " << result6 << endl;
    cout << "期望: 15 (最底层最左边的节点，虽然是右子树)" << endl;
    
    // 测试案例7: 不平衡树 [1,2,3,4,null,null,null,8,9]
    cout << "\n测试案例7: [1,2,3,4,null,null,null,8,9]" << endl;
    TreeNode* root7 = createNode(1);
    root7->left = createNode(2);
    root7->right = createNode(3);
    root7->left->left = createNode(4);
    root7->left->left->left = createNode(8);
    root7->left->left->right = createNode(9);
    
    int result7 = solution.findBottomLeftValue(root7);
    cout << "输入: [1,2,3,4,null,null,null,8,9]" << endl;
    cout << "输出: " << result7 << endl;
    cout << "期望: 8 (最底层最左边的节点)" << endl;
    
    // 测试案例8: 复杂情况 [5,4,8,11,null,13,4,7,2,null,null,null,1]
    cout << "\n测试案例8: [5,4,8,11,null,13,4,7,2,null,null,null,1]" << endl;
    TreeNode* root8 = createNode(5);
    root8->left = createNode(4);
    root8->right = createNode(8);
    root8->left->left = createNode(11);
    root8->right->left = createNode(13);
    root8->right->right = createNode(4);
    root8->left->left->left = createNode(7);
    root8->left->left->right = createNode(2);
    root8->right->right->right = createNode(1);
    
    int result8 = solution.findBottomLeftValue(root8);
    cout << "输入: [5,4,8,11,null,13,4,7,2,null,null,null,1]" << endl;
    cout << "输出: " << result8 << endl;
    cout << "期望: 7 (最底层最左边的节点)" << endl;
    
    // 释放内存
    deleteTree(root1);
    deleteTree(root2);
    deleteTree(root3);
    deleteTree(root4);
    deleteTree(root5);
    deleteTree(root6);
    deleteTree(root7);
    deleteTree(root8);
    
    cout << "\n=== 测试完成 ===" << endl;
    
    return 0;
}